package com.ftg.learn.day12.datastruct;

import javax.swing.*;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 最简单的树
 *
 * @author 布衣
 */
public class LearnTree {

    List<Integer> nlrList = new ArrayList<>();
    List<Integer> lnrList = new ArrayList<>();
    List<Integer> lrnList = new ArrayList<>();

    private int size;

    private Node root;

    /**
     * 树的基础节点
     */
    private class Node {

        private int data;
        private Node left;
        private Node right;

        public Node() {
        }

        public Node(int data) {
            this.data = data;
        }

        public Node(Node left, int data, Node right) {
            this.left = left;
            this.data = data;
            this.right = right;
        }
    }

    public boolean insert(int value) {
        this.size++;
        return add(root, value);
    }

    public int size(){
        return this.size;
    }


    /**
     * 先序
     * @param current
     */
    public void nlr(Node current){
        if(current == null){
            return;
        }
        System.out.println(current.data);
        nlrList.add(current.data);
        nlr(current.left);
        nlr(current.right);
    }

    public void 先序遍历(){
        nlr(root);
    }

    public void lnr(Node current){
        if(current == null){
            return;
        }
        lnr(current.left);
        System.out.println(current.data);
        lnrList.add(current.data);
        lnr(current.right);
    }

    public void 中根遍历(){
        lnr(root);
    }

    public void lrn(Node current){
        if(current == null){
            return;
        }
        lrn(current.left);
        lrn(current.right);
        lrnList.add(current.data);
        System.out.println(current.data);
    }

    public void 后根遍历(){
        lrn(root);
    }

    //平衡二叉树的左旋转
    public void leftRotate(Node current){
        Node temp = current.right;
        current.right = temp.left;
        temp.left = current;
        current = temp;
    }

    //平衡二叉树的右旋转
    public void rightRotate(Node current){
        Node temp = current.left;
        current.left = temp.right;
        temp.right = current;
        current = temp;
    }

    /**
     * 计算一个数组中可以容纳的雨水总量。
     * 该方法使用双指针法，从数组的两端开始向中间移动，同时维护左右两边的最大高度。
     * 这种方法的优点是时间复杂度较低，只需要遍历一次数组。
     *
     * @param height 表示每个位置的高度的数组。数组的长度必须大于等于2。
     * @return 返回可以容纳的雨水总量。
     */
    public int trap(int[] height) {
        /* 初始化答案为0，用于累加雨水总量 */
        int ans = 0;
        /* 初始化左右指针 */
        int left = 0, right = height.length - 1;
        /* 初始化左右两边的最大高度为0 */
        int leftMax = 0, rightMax = 0;
        /* 当左指针小于右指针时，循环继续 */
        while (left < right) {
//            [0,1,0,2,0,0,3,2,1]
            /* 更新左邊的最大高度 */
            leftMax = Math.max(leftMax, height[left]);
            /* 更新右边的最大高度 */
            rightMax = Math.max(rightMax, height[right]);
            /* 如果左边的高度小于右边的高度，说明右边的墙可以挡住左边的雨水 */
            if (height[left] < height[right]) {
                /* 累加可以容纳的雨水量，并将左指针向右移动 */
                ans += leftMax - height[left];
                ++left;
            } else {
                /* 如果右边的高度小于等于左边的高度，说明左边的墙可以挡住右边的雨水 */
                /* 累加可以容纳的雨水量，并将右指针向左移动 */
                ans += rightMax - height[right];
                --right;
            }
        }
        /* 返回可以容纳的雨水总量 */
        return ans;
    }


    private  boolean add(Node current, int val) {
        if (current == null) {
            //空树
            root = new Node(null, val, null);
            return true;
        }
        int compare = current.data - val;
        Node temp = compare > 0 ? current.left : current.right;
        if (temp != null) {
            add(temp, val);
        } else {
            Field left = null;
            try {
                left = current.getClass().getDeclaredField(compare > 0 ? "left" : "right");
                left.setAccessible(true);
                left.set(current, new Node(val));
            } catch (NoSuchFieldException | IllegalAccessException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        LearnTree learnTree = new LearnTree();
        learnTree.insert(60);
        learnTree.insert(45);
        learnTree.insert(10);
        learnTree.insert(70);
        learnTree.insert(65);
        learnTree.insert(55);
        learnTree.先序遍历();
        System.out.println(learnTree.nlrList);

        learnTree.中根遍历();
        System.out.println(learnTree.lnrList);

        learnTree.后根遍历();


//        什么叫树?  二叉树 ? 满二叉树 ?树的遍历  ？ 先根  中根  后根
//        递归  dfs(深度优先)  bfs（广度优先）

//        BST : 二叉搜索树 不平衡的

    }


}
